package com.xinwei.leetcode.数组;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

// https://leetcode-cn.com/problems/combinations/
public class _77_组合 {
    List<List<Integer>> lists = new ArrayList<>();
    int border = 0;

    public List<List<Integer>> combine(int n, int k) {
        Deque deque = new LinkedList<Integer>();
        border = k;
        combine(n, 1, deque, -1);
        return lists;
    }

    private void combine(int n, int depth, Deque deque, int cur) {
        // 如果 当前深度+剩下的数字 达不到目标个数，则直接返回
        if (depth + n - cur - 1 < border) {
            return;
        }

        // 如果已经达到目标个数的组合，保存
        if (depth > border) {
            lists.add(new ArrayList<>(deque));
            return;
        }

        // 组合
        for (int i = cur + 1; i < n; i++) {
            deque.push(i + 1);
            combine(n, depth + 1, deque, i);
            deque.pop();
        }
    }


    /**
     * 对上面的代码进行优化剪枝
     */
    public List<List<Integer>> combine1(int n, int k) {
        Deque deque = new LinkedList<Integer>();
        border = k;
        combine(n, 1, deque, -1);
        return lists;
    }

    private void combine1(int n, int depth, Deque deque, int cur) {
        // 如果已经达到目标个数的组合，保存
        if (depth > border) {
            lists.add(new ArrayList<>(deque));
            return;
        }

        // 组合
        // depth + n - (cur + 1) >= border
        // 所以 cur <= depth + n - 1 - border
        for (int i = cur + 1; i < depth + n - border; i++) {
            deque.push(i + 1);
            combine(n, depth + 1, deque, i);
            deque.pop();
        }
    }
}
